#include <iostream>
#include <cmath>
#include <vector>


namespace {

// (a/2)^2 >= a
int sqrt(int x) {
    if (x == 0) return x;

    int left = 1;
    int right = x/2;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        int r = mid * mid;
        if (r > x)
            right = mid - 1;
        else
            left = mid;
    }
    return left;
}

// 牛顿法
// x1 = (x0 + x / x0) / 2
int sqrt2(int x) {
    if (x < 2) return x;

    double last = x;
    double next = (last + x / last) / 2;
    // std::cout.precision(10);
    while (abs(last-next) >= 1) {
        last = next;
        next = (last + x / last) / 2;
        std::cout << "last " << last << " next " << next << std::endl;
    }
    return next;
}

typedef std::vector<int> VectorInt;
int BinarySearch(VectorInt &nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    // search in [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // std::cout << "mid " << mid << " num " << nums[mid] << std::endl;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) { // [left = mid + 1, right]
            left = mid + 1;
        }
        else if (nums[mid] > target) { // [left, right = mid - 1]
            right = mid - 1;
        }
    }
    return -1;
}

int BinarySearchLeft(VectorInt &nums, int target) {
    int left = 0;
    int right = nums.size();
    if (right == 0) return -1;

    // search in [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        std::cout << "mid " << mid << " num " << nums[mid] << std::endl;
        if (nums[mid] == target) {
            right = mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid;
        }
    }
    if (left == nums.size()) return -1;
    return nums[left] == target ? left : -1;
}

int BinarySearchRight(VectorInt &nums, int target) {
    int left = 0;
    int right = nums.size();

    // search in [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        // std::cout << "mid " << mid << " num " << nums[mid] << std::endl;
        if (nums[mid] == target) {
            left = mid + 1;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid;
        }
    }
    if (left == 0) return -1;
    return nums[left-1] == target ? left-1 : -1;
}

VectorInt BinarySearchAll(VectorInt &nums, int target) {
    VectorInt ret = {-1, -1};
    int left = 0;
    int right = nums.size();
    if (right == 0) return ret;

    // search in [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid;
        }
    }

    if (left == nums.size() || nums[left] != target) return ret;

    ret[0] = left;
    right = nums.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid;
        }
    }

    ret[1] = left - 1;
    return ret;
}

/*
峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞
*/
int FindPeakElement(VectorInt &nums) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

void Handle() {

    int x = 99;
    std::cout << "sqrt(" << x << ") = " << sqrt(x) << std::endl;
    std::cout << "sqrt2(" << x << ") = " << sqrt2(x) << std::endl;

    VectorInt nums = {1,1,3,3,3,4,5,6,7,8,9,9,10,11};
    std::cout << "nums: ";
    for (auto iter = nums.begin(); iter != nums.end(); iter++) {
        std::cout << *iter << ",";
    }
    std::cout << std::endl;
    int target = 3;
    int index = BinarySearch(nums, target);
    std::cout << "binary search " << target << " index " << index << std::endl;

    index = BinarySearchLeft(nums, target);
    std::cout << "binary search left " << target << " index " << index << std::endl;

    index = BinarySearchRight(nums, target);
    std::cout << "binary search right " << target << " index " << index << std::endl;

    VectorInt targets = {7,1,9,0,12};
    for (auto iter = targets.begin(); iter != targets.end(); iter++) {
        target = *iter;
        VectorInt ret = BinarySearchAll(nums, target);
        std::cout << "binary search all " << target << " index " << ret[0] << "," << ret[1] << std::endl;
    }
    index = FindPeakElement(targets);
    std::cout << "find peak element " << " index " << index << std::endl;
}

}

void HandleBinarySearch() {
    Handle();
}